[LINUX] Summarize what you learned about OS memory management

Introduction

I go to the University of the People, a free online university (USA). All classes are in English, but the level is quite low, maybe around 400,000 and you can get a bachelor's degree from the American Bachelor of Degrees. What it helps depends on the person, but I do it just because I want to say I've graduated from college. I chose a better university if I had the money, but at that time I had 170,000 take-homes and had no choice.

Well, I took an OS class in that CS (computer science). It was difficult and interesting, so I'd like to summarize it here so I don't forget it. 9 weeks class, 8th week from tomorrow. I can't keep up with reading the text, and I haven't published more than half of the journals, so I should know the level of understanding. I'll write this article to sort out what I know and don't know.

textbook

http://pages.cs.wisc.edu/~remzi/OSTEP/

The memory is Chapter 12-24. I was surprised that it was thicker than I expected.

What i don't know

--Since the story of CPU is mixed, the barriers between OS, CPU (MMU/TLB), RAM, and Swap are not well understood. ――I really want to think about it in connection with Linux that I usually use, so I'm not sure because it is mixed with pseudo ideal theory.

Start

Story before Chapter 12

At the beginning, the main story is about the CPU. The important thing in that --All instructions (instructions to the CPU, calculations, that is, app code) need to be stored in memory --Do not handle physical memory directly, but treat it as virtual memory. From the OS's point of view (roughly speaking), all hardware is viewed through virtual filters. All hardware is treated as a VM. That's why linux kernel parameters are often named vm_. It's not a VM of ESXi/KVM, it's a machine with hardware, and it's a virtual machine. VM. In this class, VM is all about that. Personally, I would like to call it VHW because it is a virtual H/W. Around weeek 1-2, the task of clarifying the two VMs and context was raised. good. The reason why you need to use vm is also in the first half of the textbook, so if you are interested, please do.

It's interesting to talk about things here and there.

Chapter 13 Address Spaces code

It's easy if the OS manages memory. Developers can't care about the memory area used by other processes, so do it. The address space puts the stack in front and the heap behind. The center is an unused area, and the area is expanded toward the center. I don't really understand this difference.

To make virtual memory (a context that virtually sees the RAM itself, not the RAM that is placed on the disk) without directly handling the physical memory, for example, you want to run an app with 2G or more even if you have only 1G of memory. Then there is no choice but to use virtual memory, isn't it?

At that time, the addresses of physical memory and virtual memory will be different. This difference is the beginning of everything.

3 goals

  1. Don't let the developer care about memory
  2. Efficient management (for example, if you have a 4G conversion table to manage 4G memory, that's it)
  3. Make it secure (it would be dangerous if the area used by A was erased by B)

Chapter 14 Memory API

The stack is the area that is * automatically * allocated when int x; is specified in C-lang.

The story of C malloc (), free ().

Reserve an appropriate area for both int and double. free () will be released. When process dies, all areas are automatically freed. This is also the role of the OS.

A function that asks the OS to "give me memory" is called an API. It means API provided by the OS.

Chapter 15 Address Translation

The confusion begins here. The story of converting physical and virtual addresses. The word "logical address" is ambiguous, so I don't use it, and I feel that it rarely appears in textbooks.

It's painful because the assembly comes out, but I've touched it in the previous class (I forgot the name, maybe it was CS1105), so I'll read it somehow. What the assembly does is represent a bucket relay between CPU-register-memory. If you want to copy a to b, put a in a register. Put the register in b. The register may be eax or named ebx. maybe.

The OS creates a page table at startup. I think this is the reason why you cannot change the memory capacity while the OS is booting, because you can create a table that matches the capacity of the physical memory. Then initialize is done. Important areas of the kernel (trap, system call handler etc) are secured (I wonder if this was another chapter)

What was interesting was the role bridging flow diagram, where the hardware was between the OS and the program. If you think it's hw, os, program, it's os, hw, program. The OS commands, the CPU calculates, and returns the result to the program. The program issues instructions via the OS with a system call as needed.

The OS uses a timer to stop/restart the process in order to do a context switch. Each time, the CPU registers are replaced with process-specific contents.

internal flagmentation On Linux, the page size is fixed at 4K. Even if I want 1 byte of data, I will use 4KB. This waste is called internal flagmentation. This will come out later.

Chapter 16 Segmentation

segmentation fault You see it often, it comes out when an incorrect address is specified. For example, if there is an area of ​​start: 0 size: 8 and an access of start: 5 comes, it will be faulted because it is not the correct start point though it is in the data. maybe. This start point is called offset. maybe.

Each memory area has a metadata area, such as a protection bit. You can check r/w authority.

process A uses 1G. B uses 2G. At this time, what is the minimum division unit of memory? The story. I was so confused here that I read the textbook many times.

After all, it is easier to understand when compared with the paging that will come out later

Segmentaion: Dynamically change page size Paging: Fixed size (4K for Linux)

At first, I was super confused because I had a one-functional view of segmentation in paging.

Both have Pros and Cons, but segmentation has a large overhead and Paging seems to be the mainstream. If the starting points of the addresses are different, you may have to follow the node from the head, or you may not be able to use the paging / buddy system double-tree structure (high-speed fetch) described later. It's an advantage that internal flagmention doesn't occur because we only secure what we need. But the price is external flagmentation. For example, let's say that the 1K, 3K, and 2K areas are vacant. I want to arrange them in a 6K area, but if there is no continuous space anywhere, then I'd like to replace the place where I'm using 1K ... Where is the 1K guy? As a result, it is difficult to find a place where everything can be stored.

Hmm? How do you find a place you aren't using? → Go to the next chapter

Chapter 17 Free Space Management

This chapter was interesting. How does the OS manage unused space? Well, yes, you need to * use * the knowledge that you aren't using it to recognize where you aren't using it. I had never thought about it.

There are talks about Slab allocator and Buddy allocator (used on Linux, try cat/proc/buddy *).

You specify the capacity with malloc (size), but you don't need the size with just free (variable name). This is possible because the allocator has capacity on the table.

When asked to give me a 1M area and multiple areas are free, how does the allocator choose it? best hit = Lick everything and return the minimum area. worst fit = Use a huge area. Then it seems easy to enter! It's worst because it's inefficient. First hit = Use enough space first found. And so on.

Buddy allocator Record the free space with a double search tree of 2 to the nth power. If it is 64byte memory, 32byte * 2 will hang below it. If one 32B is used and the request is 32 bytes, it is easy to make a judgment that you have to bet on the other 32 bytes.

As with buddy and slab allocator, the problem is that they are vulnerable to scaling. If the physical memory increases or decreases on the way, Nihongi will collapse if it is buddy.

There is only an introduction that the glibc allocator is real world, but I haven't been able to research it yet.

Anyway, the allocator is complicated and there are various things, and it's amazing.

Chapter 18 Introduction to Paging

The story of paging. Address translation is easy at high speed in a fixed size area.

I was not good at memory address conversion calculation. 0x011234 is divided into VPN (Virtual page number) and offset. VPN = 01 offset = 1234 There is a VPN conversion in the conversion table. For example, 01 is a certain chome with a virtual address, which corresponds to a physical 32nd chome. offset is the street address, which is not converted. If it is a virtual address, it will be 1-1234, and if it is a physical address, it will be 32-1234.

Example Linux page size is fixed at 4K. If the memory is 128K, the number of pages needs to be 128/4 = 32 pages. When 32 is represented by binary (binary), 2 ** 5 = 5bit is required. The upper 5 bits of the requested address are translated, and the rest is set as offset and goes to the physical address as it is.

Here are some additional judgment bits.

valid bit: The unused area is invalid, so if it is not expected, a trap will be thrown to the OS. The OS kills the process.

dirty bit: Stands when there is a rewrite. It will appear in the later Chapter: page replacement, but it is used for purposes such as preventing unnecessary paging.

I forgot which chapter, so I'll write it here, but the protection bit is important. It cannot be read by other processes. I can't read it with the kernel. In the 2018 (dake) spectrum/heart breeding issue, the memory space for the kernel and user process was completely separated. Please note that it is written in the same place as the literature around kernel 2.6, which is often found in Japanese.

Figure 18.7: A Virtual (And Physical) Memory Trace was completely incomprehensible.

The turmoil is accelerating. The story of this conversion table is about OS + RAM. In the next chapter, the TLB will come out and explode.

Chapter 19 Translation Lookaside Buffers

TLB caches the translation table instead of caching the address-translation cache. Memory contents.

It's important, so I'll say it again! !!

** TLB is address-translation cache. **

This is my selfish summarize, but I think it's like this, maybe

Normal time

show program: instruction variable x to cpu cpu: I don't know the location of x Hey OS, tell me os: The conversion table (it's slow because it's in RAM) is at 2-5. cpu: I got it

If you have a TLB

show program: instruction variable x to cpu cpu: Hey, do you know the location of TLB, x? tlb: Pyon who came a while ago. It's 2-5, Pyon (it's super fast because it's in the cpu) cpu: I got it

Since it is the CPU that first receives the information "I want x", it is quick when the "conversion work" is completed in the CPU (TLB-hit). It's slow when I go to the OS. It's slow to get to RAM, but it can't be helped. If it is in the register of the CPU, it is explosively fast. If it is not in the TLB, how to reduce the TLB-miss. TLB-miss and perform the TLB-hit at high speed leads to the eternal challenge of page replacement.

No, I'm glad I wrote this article. I understood a lot. This summarize is now possible. I'm glad I reviewed it. It's important to have a margin. You don't have to rush this week because you've already finished the assignments. If you can afford it, you can understand the meaning of the textbook! !! !! !! It's important to have a margin! !! !!

Chapter 20 Advanced Page Tables

There are talks about making paging segmentation and hybrid, and having a multi-level page table. In short

--When the page table becomes large, it takes time to fetch. --No hit when page table becomes small

In order to solve this conflicting problem, I think that it is a story to make a stage until fetch is fast → hit is easy with a multi-stage stance such as a small table, a slightly large table, a large table. I can't read it carefully because I can't afford it.

linux had 4 layers, but I feel that it has become possible to have 5 layers from around kernel 3? 4 ?.

I tried to change the page size and measure the performance, and tweeted this.

Chapter 21 Swapping: Mechanisms

Ah swap-like content. If you don't have enough memory, you'll use the HDD. you're late. But I'm happy with the virtual address! Target.

There is also an upper limit on swap. Because you make an address translation table first, right? That is the upper limit.

Certainly, it became.

Chapter 22 Swapping: Policies

This was interesting. The challenge is "what is the OS doing to reduce paging in/out?" I'm just tired, so I'm sorry for the tweet excerpt.

In a word, if you know the future, you can make the best choice, but of course it is impossible, so I feel like selecting "I wonder if this will happen somehow" from the information I have.